package com.zhugang.week11;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: translateNum
 * @author: chanzhugang
 * @create: 2022/09/04 13:13
 */
public class TranslateNum {

    /**
     * 剑指offer 46 把数字翻译成字符串
     *
     * @param num
     * @return
     */
    public int translateNum(int num) {
        // 0-a、 1-b、 2-c、.... 25-c, 有多少种不同翻译方法
        // 每个阶段从1个或者2个数字翻译
        // dp[i] = dp[i - 1] + dp[i - 2](不超过25)
        if (num <= 9) {
            return 1;
        }
        // 把十进制数转化为数字数组
        List<Integer> digitList = new ArrayList<>();
        while (num != 0) {
            digitList.add(num % 10);
            num = num / 10;
        }
        int n = digitList.size();
        int[] digits = new int[n];
        for (int i = 0; i < n; i++) {
            digits[i] = digitList.get(n - i - 1);
        }

        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            // 爬楼梯模型
            dp[i] = dp[i - 1];
            if (i - 2 >= 0 && isVaid(digits[i - 2], digits[i - 1])) {
                dp[i] += dp[i - 2];
            }

        }
        return dp[n];
    }

    /**
     * @param a
     * @param b
     * @return
     */
    private boolean isVaid(int a, int b) {
        // 十位数和个位数 和25比较
        if (a == 1) {
            return true;
        }
        if (a == 2 && b >= 0 && b <= 5) {
            return true;
        }
        return false;
    }
}